/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/combinations
   @Language: C++
   @Datetime: 16-02-09 05:45
   */

class Solution {
	void combinecore(int n,int k,int start
			,vector<vector<int> > &vs,vector<int> &v){
		if (v.size()==k){
			vs.push_back(v);
			return;
		}
		// the number of i~n must >= left element count (k-v.size)
		for (int i=start; i<=n && n-i+1>=k-v.size(); ++i){
			v.push_back(i);
			combinecore(n,k,i+1,vs,v);
			v.pop_back();
		}
	}

public:
	/**
	 * @param n: Given the range of numbers
	 * @param k: Given the numbers of combinations
	 * @return: All the combinations of k numbers out of 1..n
	 */
	vector<vector<int> > combine(int n, int k) {
		// write your code here
		vector<vector<int> > vs;
		if (n<k) return vs;	// no enough element to be selected
		vector<int> v;
		combinecore(n,k,1,vs,v);
		return vs;
	}
};
